package com.leet.code.lcof;

import com.algorithm.model.ListNode;
import com.algorithm.model.ListNodeService;

public class Code25 {

    public static void main(String[] args) {
        int[] i1 = {-10, -9, -6, -4, 1, 9, 9};
//        int[] i1 = {1, 2, 4};
        int[] i2 = {-5, -3, 0, 7, 8, 8};
//        int[] i2 = {1, 3, 4};
        ListNode listNode = new Code25().mergeTwoLists(ListNodeService.getByArray(i1), ListNodeService.getByArray(i2));
        ListNodeService.print(listNode);

    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode tmp, tmp2;
        if (l2 == null) {
            return l1;
        }
        if (l1 == null) {
            return l2;
        }

        if (l2.val < l1.val) {
            tmp = l1;
            l1 = l2;
            l2 = tmp;
        }

        ListNode l1z = l1, l2z = l2;

        while (l1z.next != null) {

            while (l2z != null && l2z.val >= l1z.val && l2z.val <= l1z.next.val) {
                tmp = l1z.next;
                l1z.next = l2z;
                tmp2 = l2z.next;
                l2z.next = tmp;
                l2z = tmp2;
            }

            l1z = l1z.next;

        }

        if (l2z != null) {
            l1z.next = l2z;
        }

        return l1;

    }

}
